package leetcode.string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

public class Lc438 {

    public List<Integer> findAnagrams(String s, String p) {

        List<Integer> ans = new ArrayList<>();
        if (s.length() < p.length()) return ans;
        HashSet<Character> pSet = new HashSet<>();
        int[] cnt = new  int[26];
        int sum = p.length();
        for (int i = 0; i < p.length(); i++) {
            pSet.add(p.charAt(i));
            cnt[p.charAt(i) - 'a']++;
        }
        int[] origin = new int[26];
        for (int i = 0; i < cnt.length; i++) {
            origin[i] = cnt[i];
        }
        for (int i = 0, j = 0; j < s.length(); j++) {
            char c = s.charAt(j);
            if (pSet.contains(c)) {
                if (cnt[c - 'a'] > 0) {
                    cnt[c - 'a']--;
                    sum --;
                    if (sum == 0) { //找到易位数了
                        ans.add(i);
                        cnt[s.charAt(i) - 'a']++;
                        sum++;
                        i++;//左节点往右移动一位
                    }
                } else  { //cnt[c - 'a'] == 0, c字符多了，找到左边的c字符，移动到其下一位
                    while (s.charAt(i) != c) {
                        cnt[s.charAt(i) - 'a']++;
                        sum++;
                        i++;
                    }
                    i++;
                }

            } else {
                while (i < j) {
                    cnt[s.charAt(i) - 'a']++;
                    sum++;
                    i++;
                }
                i = j + 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        Lc438 lc438 = new Lc438();
        String s1 = "abab";
        String s2 = "ab";
        System.out.println(lc438.findAnagrams(s1, s2));
    }
}
